Prior art page printers typically capture an entire page before any image is placed on paper. In such printers, formatting is either performed on the host computer (with large volumes of rasterized data being shipped to the printer), or on a formatter within the printer, Since a laser print "engine" operates at a constant speed, if new rasterized data is not available at a rate that keeps up with the engines's operation, a print "overrun" occurs and the page is not printable.
To prevent print overruns, a variety of techniques are in use. In one, a full raster bit map of an entire page is stored so that the print mechanism always has rasterized data awaiting action. At 300 dots per inch resolution, this technique requires approximately a megabyte of raster memory for each page. At 600 dots per inch, four megabytes of memory are required. Additionally, because laser printers achieve their rated speeds by pipelining of raster data, additional raster memory is needed to run the printer at its rated speed. Otherwise, composition of a following page cannot begin until a prior page has been ejected to the printer's output tray. To maintain the cost of laser printers at a low level, substantial efforts have been directed to reducing the amount of required raster memory.
One technique for memory reduction involves the construction of a page description. The page description is built in two steps: during formatting, data received from a host computer is converted into a list of simple commands, called display commands, that describe what must be printed. The second step prepares the display command list for printing and entails a parsing of the display commands and a rendering of the described objects into a raster bit map. This procedure requires a full page raster bit map memory because the same memory is used for succeeding pages.
To reduce the amount of required memory, the display command list procedure has been modified by sorting display commands according to their vertical position on a page. The page is then divided into sections called page strips or "page intermediate", and each page strip is passed, sequentially, to the print engine for printing. When display commands within a page strip are rendered into rasterized data at a fast enough pace, the same memory used to store a first page strip can be reused for a subsequent page strip further down the page (once the first page strip has been transferred to paper).
The Laser Jet III Laser Printer, manufactured by the Assignee of this application, employs a display command list algorithm and utilizes three raster buffers. The first buffer is reused on the fourth strip of a page; the second buffer is reused on the fifth strip, etc. For an eight page per minute printer, little time is left between the finishing of strip one and the time when strip four will be required by the print mechanism. If the strip is not delivered in time, a "print overrun" occurs and the page is incorrectly printed.
In U.S. patent application Ser. No. 07/701,235, entitled "Method and Apparatus For Preventing Print Overruns", assigned to the same Assignee as this application, a page printer determines total rasterization execution time for all display commands in each strip. If a strip's rasterization execution time exceeds a predetermined value, the strip is prerasterized, so as to reduce the time required during subsequent transfer of data to the print mechanism. The disclosure of the aforesaid patent application is incorporated herein by reference.
Most recently, 600 dot per inch resolution printers have been introduced to the marketplace. Such printers handle not only text but also line art and various types of images. To minimize the amount of memory required in such printers, data compression techniques are employed. For instance, run length data compression is used by host processors in the process of data transfer to the printer. In a run length encoding scheme, data that repeats is encoded by indicating the identity of the data and the run length of the repeat. Run length compression is successful when used with text and line art. When used with image data, however, such a compression scheme is much less satisfactory.
Certain types of images are classified as either "ordered dither" or "error diffused". An ordered dither image (also called "clustered") is a half-tone image that includes half-tone grey representations throughout the page. Such images generally reflect substantial data redundancy and lend themselves to lossless techniques of data encoding (e.g. run length). Error diffused images (also called "dispersed"), by contrast, exhibit little redundancy in their data and require different methods of compression. As a result, the use of a single data compression scheme in a page printer no longer enables such a printer to handle image data--while still maintaining a minimal amount of on-board raster memory.
In additional to run-length encoding, the prior art is replete with other data compression schemes. For instance, in U.S. Pat. No. 4,558,302 to Welch, the well known Lempel/Ziv/Welch (LZW) data compression technique is described. That procedure compresses an input data stream by storing, in a string table, strings of characters encountered in an input data stream. A "compressor" searches the input stream to determine the longest match to a stored string. As the compressor encounters more and more strings, it becomes "smarter" and enables succeedingly longer runs of characters to be compressed. Each match of an input string of characters to a stored table string causes a code to be transmitted to a receiver, where an identical string table resides that enables a decoding of the transmission.
Run length data compression on printer raster scan lines is described by Spivey in "Data Compression Technique for APA Printer (Change Block Skipping)" and "Hybrid Data Compression Technique for Change Block Skipping in an APA Printer", IBM Technical Disclosure Bulletin, vol. 23, No. 12, May 1981, pages 5464-5470. Spivey's procedure compares a current scan line to a corresponding scan line in a previous image and outputs codes in dependence upon the concurrence or lack of concurrence therebetween. Spivey also describes a hybrid technique which employs the aforesaid method in combination with run-length encoding.
Accordingly, it is an object of this invention to provide a page printer that includes a system for data compression and is adaptive in response to characteristics of received data.
It is another object of this invention to provide a page printer that employs a system that intelligently selects a data compression technique so as to enable efficient use of a limited amount of on-board memory.
It is yet another object of this invention to provide a page printer with a system for data compression, which system is selectively called upon when on-board memory is in a state where printing cannot continue unless data compression occurs.
It is still another object of this invention to provide improved data compression techniques for use in a page printer.